/*
https://leetcode-cn.com/problems/unique-paths

一个机器人位于一个 m x n 网格的左上角，机器人每次只能向下或者向右移动一步。
机器人试图达到网格的右下角，问总共有多少条不同的路径？

示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向右 -> 向下
3. 向下 -> 向下 -> 向右

示例 2:
输入: m = 7, n = 3
输出: 28

*/

class Solution {
public:
    int uniquePaths(int m, int n) {
    /*
    提示：动态规划求解
    令 dp[(i, j)] 是从左上角 (0, 0) 到达 (i, j) 的不同路径数量，
    状态转移方程为：dp[(i, j)] = dp[(i-1, j)] + dp[(i, j-1)]
    注意，对于索引为零的行 dp[(0, j)]，或者索引为零的列 dp[i][0]，由于都是在边界，所以只有一种到达方式。
    */
        if (m <= 0 || n <= 0)
            return 0;

        int dp[m][n] = {0};
        dp[0][0] = 1;  // 从左上角到左上角只有 1 种走法，就是不走
        for (int i = 0; i < m; ++i)  // 边界索引为 0 的列都只有一种到达方式
            dp[i][0] = 1;
        for (int j = 0; j < n; ++j)  // 边界索引为 0 的行都只有一种到达方式
            dp[0][j] = 1;

        for (int i = 1; i < m; ++i)
            for (int j = 1; j < n; ++j)
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        return dp[m - 1][n - 1];
    }
};